/* 栈相关操作:

 设计一个有getMin功能的栈；
 由两个栈组成的队列;
 将栈底元素返回并移除;
 递归函数逆序一个栈；
 实现栈的排序；
 生成窗口最大值数组；
 
 */
 
//设计一个有getMin功能的栈
public class Mystack1{
	private Stack<integer> stackData;
	private Stack<Integer> stackMin;
	 
	public Mystack1(){
		this.stackData = new Stack<integer>();
		this.stackMin = new Stack<integer>();
	}
	public void push(int newNum){
		if(this.stackMin.isEmpty()){
			this.stackMin.push(newNum);
		}else if(newNum<this.stackMin.peek()){
			this.stackMin.push(newNum);
		}else{
			int newMin = this.stackMin.peek();
			this.stackMin.push(newMin);
		}
		this.stackData.push(newNum);
	}
	public int pop(){
		if(this.stackData.isEmpty()){
			throw new RuntimeException("Your stack is empty!");
		}
		this.stackMin.pop();
		return this.stackData.pop();
	}
	public int getmin(){
		if(this.stackMin.isEmpty()){
			throw new RuntimeException("Your stack is empty!");
		}
	}
	return this.stackMin.peek();
}
 
//两个栈组成队列
public class TwoStacksQueue{
	public Stack<Integer> stackPush;
	public Stack<Integer> stackPop;
	 
	public TwoStacksQueue(){
		stackPush = new Stack<Integer>();
		stackPop = new Stack<Integer>();
	}
	public void add(int pushInt){
		stackPush.push(pushInt);
	}
	 
	public int poll(){
		if(stackPush.isEmpty() && stackPop.isEmpty()){
			throw new RuntimeException("Queue is empty!");
		}else if(stackPop.isEmpty()){
			while(!stackPush.isEmpty()){
				stackPop.push(stackPush.pop());
			}
		}
		return stackPop.pop();
	}
	 
	public int peek(){
		if(stackPush.isEmpty() && stackPop.isEmpty()){
			throw new RuntimeException("Queue is empty!");
		}else if(stackPop.isEmpty()){
			while(!stackPush.isEmpty()){
				stackPop.push(stackPush.pop());
			}
		}
		return stackPop.peek();
	}
}
 
//将栈底元素返回并移除
public int getAndRemoveLastElement(Stack<Integer> stack){
	int result = stackPop();
	if(stack.isEmpty()){
		return result;
	}else{
		int last = getAndRemoveLastElement(stack);
		stack.push(result);
		return last;
	}
}

//递归函数逆序一个栈
 public void reverse(Stack<integer> stack){
	 if(stack.isEmpty()){
		 return;
	 }
	 int i =getAndRemoveLastElement(stack);
	 reverse(stack);
	 stack.push(i);
 }
 
//实现栈的排序
public void sortStack(Stack<Integer> stack){
	Stack<integer> help = new Stack<integer>();
	while(!stack.isEmpty()){
		int cur = stack.pop();
		while(!help.isEmpty() && help.peek()>cur){
			stack.push(help.pop());
		}
		help.push(cur);
	}
	while(!help.isEmpty()){
		stack.push(help.pop());
	}
}

//生成窗口最大值数组
public int[] getMaxWindow(int[] arr, int w){
	if(arr==null || w<1 || w>arr.length){
		return null;
	}
	LinkedList<Integer> qmax = new LinkedList<integer>();
	int[] res = new int[arr.length-w+1];
	int index =0;
	while(int i=0;i<arr.length;i++){
		while(!qmax.isEmpty() && arr[qmax.peekLast()]<=arr[i]){
			qmax.pollLast();
		}
		qmax.addLast(i);
		if(qmax.peekFirst()==i-w){
		qmax.pollFirst();
		}
		if(i>=w-1){
			res[index++]=arr[qmax.peekFirst()];
		}
	}
	return res;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 